// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/04/Mult.asm

// Multiplies R0 and R1 and stores the result in R2.
// (R0, R1, R2 refer to RAM[0], RAM[1], and RAM[2], respectively.)

// Put your code here.
// 通过加减法和移位来实现; 把出发转成乘法, 乘法转成假发, 减法转成加法.
// 模拟CPU运算乘法的步骤:
// 假设计算3 * 3
// 原码是0011 * 0011(四位为例)
// CPU中的乘法器过程如下:
// 3个内存分别存放乘数0011,被乘数0011 一部分积初始值为0
// 1. 首先判断乘数寄存器(目前为0011)的最低位为1. 如果为1则将部分积的值通过加法器加上被乘数 0011. 因此此部结束后积分寄存器内容为0011
// 2. 将乘数寄存器右移一位, 同时将部分积寄存器也右移一位. 同时乘积寄存器最低位溢出丢弃. 部分积寄存器高位补0, 低位溢出后填充到乘数寄存器. 因此部分积寄存器其原来的值0011 变成了0001. 乘数寄存器0011变成了1001(这里低位的1溢出,最高位被部分积溢出的1填充)
// 3. 判断乘数内存部分最低位(0001)为1. 将部分积通过加法器加上被乘数0011.因此此部结束后部分积内容是(0001+0011=0100)
// 4. 乘数右移一位,同时将部分积也右移一位. 同第二部. 因此部分积寄存器原来的值0100变成了0010. 乘数1001变成了0100, 低位1溢出, 最高位被部分积溢出的0填充
// 5. 判断乘数低位为0不做加法操作直接做第二步的移位操作. 即有了部分积变成0001, 乘数变成了0010.
// 6. 判断乘数低位为0 不做加法操作直接做第二部的移位操作. 即有了部分积变成0000, 乘数变成了1001; 此时所有乘数全部处理完毕
// 7. 最终结果将部分积作为高位, 乘数作为低位得到值为00001001换算为10进制得到9
@Shift
M = 1
@2
M = 0

@i     //i = 0
M = 0

(FOR)  //i < 16
@i
D = M
@16
D = D - A
@END
D; JGE

@1     //R2 = R2 + {R0 & [0 - [R1 & Shift]]}
D = M
@Shift
D = D & M
D = -D
@0
D = M & D
@2
M = M + D

@0     //R0 << 1
D = M
M = M + D
@Shift //SHift << 1
D = M
M = M + D

@i     //i++
M = M + 1
@FOR
0; JMP
(END)

